package com.zlk.algorithm.dataStructure.tree.treeDp;

import com.zlk.algorithm.dataStructure.tree.NodeUtils;
import com.zlk.algorithm.dataStructure.tree.TreeNode;
import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName MaxDistance
 * @description:给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离
 * @author: slfang
 * @create: 2024-02-20 15:31
 * @Version 1.0
 **/
public class MaxDistance {

    //可能性
    //    1、经过x   左数高度+右树高度
    //    2、不经过x Math.max(左树，右树)
    //信息：
    //   高度
    class Info {
        int height;
        int maxDistance;

        public Info(int height, int maxDistance) {
            this.height = height;
            this.maxDistance = maxDistance;
        }
    }

    public int maxDistance(TreeNode node){
        if(node==null){
            return 0;
        }
        return process(node).maxDistance;
    }


    public Info process(TreeNode node){
        if(node==null){
            return new Info(0,0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int height;
        int maxDistance;
        int leftHeight = leftInfo.height;
        int rightHeight = rightInfo.height;

        height =Math.max(leftHeight,rightHeight)+1;
        //经过x
        int p1 = leftHeight+rightHeight+1;

        //不经过
        int p2 = leftInfo.maxDistance;

        int p3 = rightInfo.maxDistance;
        maxDistance = Math.max(Math.max(p1,p2),p3);
        return new Info(height,maxDistance);
    }

    public  int maxDistance2(TreeNode head) {
        return process2(head).maxDistance;
    }

    public  Info process2(TreeNode x) {
        if (x == null) {
            return new Info(0, 0);
        }
        Info leftInfo = process2(x.left);
        Info rightInfo = process2(x.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int p1 = leftInfo.maxDistance;
        int p2 = rightInfo.maxDistance;
        int p3 = leftInfo.height + rightInfo.height + 1;
        int maxDistance = Math.max(Math.max(p1, p2), p3);
        return new Info( height,maxDistance);
    }



    @Test
    public void test(){
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = NodeUtils.generateRandomBST(maxLevel, maxValue);
            if (maxDistance(head) != maxDistance2(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }





}
